package org.zdw.data.structure.practice;

public class QuickPra {

    public void sort(int[] array){
        if(array.length > 0){
            sort(array,0,array.length-1);
        }
    }

    private void sort(int[] array,int low,int high){
        if(low < high){
            int middle = getMiddle(array,low,high);
            sort(array,low,middle-1);
            sort(array,middle+1,high);
        }
    }

    public int getMiddle(int[] array,int low,int high){
        int tmp = array[low];

        while(low < high){

            while (low < high && array[high] >= tmp){
                high--;
            }

            array[low] = array[high];

            while (low < high && array[low] <= tmp) {
                low++;
            }

            array[high] = array[low];

        }

        array[low] = tmp;

        return low;
    }
}
